(1) Field of the Invention
The present invention relates to localization. More particularly, the present invention relates to localization systems and methods to unambiguously determine the range, bearing, and relative heading of an object relative to a reference point.
(2) Description of the Prior Art
Localization approaches can be broadly categorized by methods that use direct measurement of range and bearing information with derived heading, or that use some form of trilateration (range-based) or triangulation (angle-based) algorithm to determine state information not directly measured. Examples of techniques that use direct measurements of range and bearing are radar, sonar, and lidar.
When the transmitter(s) and receiver(s) are co-located, range is based on either time-of-flight or frequency modulation, and bearing may be determined by using gimbaled elements or multiple elements, including phased arrays. Using the Doppler effect, the radial velocity component of a contact can be determined, but the total velocity can only be determined from a series of measurements.
Trilateration approaches to localization use measured range information to reference points about which some absolute or relative position information is known to determine a position relative to these references. An example of a trilateration system is GPS, which uses derived range information from multiple satellites serving as beacons.
A key feature of GPS is that range information is based on a known satellite broadcast schedule, which is known to all receivers. A major disadvantage of GPS is signal availability. In regions with sufficient interference such as canyons, streets surrounded by high structures, or indoors, position cannot be determined. Additionally, commercial GPS accuracy limits the ranges at which coordination of multiple agents such as autonomous mobile vehicles can practically occur.
Acoustic long and short baseline navigation systems are local trilateration techniques, and require a minimum of three reference beacons with positions known to a central controller or to the object being localized. Limitations of long baseline navigation include the requirement to accurately determine the relative locations of the beacons, the potential difficulties in placing beacons in a navigable area, and limitations in range associated with aliasing. Short baseline systems partially mitigate some of the limitations of long baseline systems, although accuracy typically decreases.
Acoustic ultra-short baseline systems use time-of-flight information to obtain range, but can calculate bearing from the phase difference of signals. For almost all acoustic baseline system applications, scalability to multi-vehicle operations is a limitation. If the configuration requires vehicles to transmit in order to localize, long periods between transmissions will result when a sufficient number of vehicles are used if signals are required to be vehicle-specific. These long periods equate to infrequent updates that make the system impractical.
Triangulation approaches to localization use measured angular information to reference points about which some absolute or relative position information is known to determine a position relative to these references. A triangulation algorithm typically requires two reference locations with a known distance between them and the angles relative to the baseline formed by these reference locations to the object to be localized to determine the relative object position.
An illustrative triangulation approach is optical three-dimensional localization using stereo vision. This approach uses two cameras with known distance and orientation relative to each other. The angles to a particular location in space taken from each of the images are used to calculate the range from each camera. Practical limitations include compensating for distortions in images from the lenses, methods to ensure the images are comparable, and the accuracy of methods to correlate features in each image.
Structured light is also based on a triangulation technique, although a paired emitter and receiver form the baseline rather than two sensors. Limitations to structured light include difficulty in detecting transparent, translucent, or reflective materials and surfaces with certain curvatures. The structured light approach would also necessitate the use of some object recognition or tracking algorithm to identify features of the object used for localization.
Object recognition is a machine learning approach to localization that does not rely on active radiation or a trilateration or triangulation algorithm in use, although information used to train the system may employ one or more of these methods. In the case of relative localization, a recognition algorithm would need to be trained with a set of images of an object from a variety of ranges and orientations. Potential disadvantages are the possibility of a large training set necessary to suitably characterize the object to be localized and the processing required to identify relevant portions of an image.
A disadvantage of all of the localization techniques described, except the object recognition approach, is that the instantaneous heading information can not be calculated from a single measurement. A time series consisting of a minimum of two positions is required to determine relative velocity. In the case of a moving reference point, such as a mobile robot, the motion of the reference must be taken into account to determine the relative velocity and heading of the localized object, meaning the actual motion of the reference point must be known.
Thus, a need has been recognized in the state of the art to provide localization systems and methods that are low cost and achievable with commonly available cameras and known image processing algorithms, while also having an accuracy comparable or better to other known localization techniques. Additionally, the systems and methods should be capable of being used in a variety of applications requiring relative range, bearing, and/or heading localization. Further, the systems and methods should enable scalable multi-agent interaction, such as coordination of multiple autonomous agents.